package study.datastructure.search.avl;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-06-25 22:48
 */

/**
 2024/6/25,
 */


public class Node {
    int key,height; //利用高度得到平衡因子
    Node left,right;
    public Node(int key){
        this.key = key;
        height=1;

    }

    //获取节点的高度
    public static int height(Node node){
        if(node==null){
            return 0;
        }
        return node.height;
    }
    //获取平衡因子
    public static int getBalance(Node node){
        if (node==null){
            return 0;
        }
        return height(node.left)-height(node.right);
    }

    //左旋
    public static Node leftRotate(Node node){
        Node rightNode=node.right;
        Node rl=rightNode.left;

        //开始旋转
        rightNode.left=node;
        node.right=rl;

        //调整高度
        node.height=Math.max(height(node.left),height(node.right))+1;
        rightNode.height=Math.max(height(rightNode.left),height(rightNode.right))+1;

        //返回新的根节点
        return rightNode;
    }

    //右旋
    public static Node rightRotate(Node node){
        Node leftNode=node.left;
        Node lr=leftNode.right;

        //开始旋转
        leftNode.right=node;
        node.left=lr;

        //调整高度
        node.height=Math.max(height(node.left),height(node.right))+1;
        leftNode.height=Math.max(height(leftNode.left),height(leftNode.right))+1;

        //返回根节点
        return leftNode;
    }

    //插入节点
    public  static Node insert(Node node,int key){
        if (node==null)
        {
            return (new  Node(key));
        }else if (key<node.key){
           node.left= insert(node.left,key);
        }else if (key>node.key){
            node.right=insert(node.right,key);
        }else {
            //重复值不允许插入
            return node;
        }

        //处理高度
        node.height=Math.max(height(node.left),height(node.right))+1;
        //插入节点时保持平衡
        int balance=getBalance(node);
        //右旋
        if (balance>1 && key<node.left.key){
            return rightRotate(node);
        }
        //左旋
        if(balance <-1 && key>node.right.key){
            return leftRotate(node);
        }

        //LR旋转
        if(balance>1 && key>node.left.key){
            node.left=leftRotate(node);
            return rightRotate(node);
        }

        //RL旋转
        if (balance<-1 &&key>node.right.key){
            node.right=rightRotate(node);
            return leftRotate(node);
        }

        return node;
    }

    //中序遍历
    public static void inOrder(Node node){
        if(node!=null){
            inOrder(node.left);
            System.out.println("key:"+node.key);
            inOrder(node.right);
        }
    }
}
